#include <iostream>
#include <vector>
#include <Eigen/Eigen>
#include "dragon.h"
#include "sparsekdtree.h"
#include "mynode.h"
#include <algorithm>
inline void swap(int &a, int &b)
{ int t = a; a = b; b = t; }


void Build(SparseKDTree& tree,Eigen::SparseMatrix<unsigned char, Eigen::ColMajor>& sparse_matrix, int cols,
           std::vector<std::vector<int>>& curlevel_allchild)
{
    if(curlevel_allchild.size()==0)
        return;
    std::vector<std::vector<int>> nextlevel_allchild;//记录下一层的所有娃
    for(int i=0; i<curlevel_allchild.size(); i++){
        //拿出当前的娃
        std::vector<int> child_id = curlevel_allchild[i];
        if(child_id.size()==1){
            //当前是个孤零零的叶子
            myNode curnode;
            curnode.boundary = 0;
            curnode.left = curnode.right = -1;
            curnode.idx = -child_id[0];
            tree.Nodes.push_back(curnode);
            continue;
        }
        //很不幸这不是个叶子。。要分割
        //先统计6*32*32个维度的最大方差和对应的维度
        float max_sigma = 0;
        int max_sigma_col;
        for(int k=0;k<cols;k++){
            float sum = 0;
            int curchild = 0;
            int nonzerorow=0;
            //求和非0元素
            for(Eigen::SparseMatrix<unsigned char, Eigen::ColMajor>::InnerIterator it(sparse_matrix, k);
                it && (curchild<child_id.size());)
            {
                if(child_id[curchild] > it.row()+1){
                    ++it;
                    continue;
                }
                else if(child_id[curchild] == it.row()+1){
                    sum += it.value();
                    ++it;
                    nonzerorow++;
                    curchild++;
                }
                else if(child_id[curchild] < it.row()+1){
                    curchild++;
                }
            }
            //if(k%10==0) std::cout<<"sum"<<k<<std::endl;
            float mean = sum/child_id.size();
            float cur_sigma = 0;
            curchild = 0;
            for(Eigen::SparseMatrix<unsigned char, Eigen::ColMajor>::InnerIterator it(sparse_matrix, k);
                it&&(curchild<child_id.size());)
            {

                if(child_id[curchild] > it.row()+1){
                    ++it;
                    continue;
                }
                else if(child_id[curchild] == it.row()+1){
                    cur_sigma += std::pow(it.value() - mean, 2);
                    ++it;
                    curchild++;
                }
                else if(child_id[curchild] < it.row()+1){
                    curchild++;
                }
            }
            cur_sigma += (child_id.size() - nonzerorow) * std::pow(0 - mean, 2);
            cur_sigma = cur_sigma / child_id.size();
            if(cur_sigma >=20000)
                std::cout<<cur_sigma<<std::endl;

            if(cur_sigma>max_sigma){
                max_sigma = cur_sigma;
                max_sigma_col = k;
            }

        }
        if(max_sigma==0){
            //又不幸发现。。这堆向量长得一毛一样。。
            //那就初始1叶子节点。。并×进去vector。。记录有多少个相同的
            myNode curnode;
            curnode.boundary = 0;
            curnode.left = curnode.right = -1;
            curnode.idx = -child_id[0];
            for(int l=0;l<child_id.size();l++){
                curnode.same.push_back(child_id[l]);
            }
            tree.Nodes.push_back(curnode);
            continue;
        }
        //然后你就是那么不幸地发现，你还是要分
        //那你很棒棒喔，记得在最大方差维度分。。
        //这时候拿出来最大方差维度的中位数。。md还要排序。。来个快排。。
        //排之前拿一列出来
        std::vector<unsigned char> sort_array;
        Eigen::SparseMatrix<unsigned char, Eigen::ColMajor>::InnerIterator it(sparse_matrix, max_sigma_col);
        for(int j=0;j<child_id.size();j++){
            if(it){
                //int cur2 = it.
                if((child_id[j]-1) == it.row()){
                    sort_array.push_back(it.value());
                    ++it;
                }
                else if(child_id[j]-1 > it.row()){
                    j--;
                    ++it;
                }
                else if(child_id[j]-1<it.row()){
                    sort_array.push_back(0);
                }
            }
            else
                sort_array.push_back(0);
        }
        std::sort(sort_array.begin(), sort_array.end(),std::greater<unsigned char>());
        unsigned char middle = sort_array[floor(sort_array.size()/2)];
        std::vector<int> leftchild_id, rightchild_id;
        int count = 0;
        while(1){
            count++;
            if(count>1)
                std::cout<<"en"<<std::endl;
            //如果真的多次循环了。。。你是真的。。很倒霉。。
            leftchild_id.clear();
            rightchild_id.clear();
            Eigen::SparseMatrix<unsigned char, Eigen::ColMajor>::InnerIterator it2(sparse_matrix, max_sigma_col);
            for(int j=0;j<child_id.size();j++){
                if(it2){
                    if(child_id[j]-1 == it2.row()){
                        if(it2.value() <= middle)
                            leftchild_id.push_back(child_id[j]);
                        else
                            rightchild_id.push_back(child_id[j]);
                        ++it2;
                    }
                    else if(child_id[j]-1 > it2.row()){
                        j--;
                        ++it2;
                    }
                    else if(child_id[j]-1 < it2.row()){
                        if(0 <= middle)
                            leftchild_id.push_back(child_id[j]);
                        else
                            rightchild_id.push_back(child_id[j]);
                    }
                }
                else{
                    if(0 <= middle)
                        leftchild_id.push_back(child_id[j]);
                    else
                        rightchild_id.push_back(child_id[j]);
                }
            }
            if(leftchild_id.size()&&rightchild_id.size())
                break;
            else if(!rightchild_id.size()){
                //右空
                middle--;
            }
        }
        myNode curnode;
        curnode.boundary = middle;
        curnode.left = tree.Nodes.size()+1+curlevel_allchild.size()-i+nextlevel_allchild.size();
        curnode.right = curnode.left+1;
        curnode.idx = max_sigma_col;
        tree.Nodes.push_back(curnode);
        nextlevel_allchild.push_back(leftchild_id);
        nextlevel_allchild.push_back(rightchild_id);
    }
    Build(tree,sparse_matrix,cols,nextlevel_allchild);
}
SparseKDTree::SparseKDTree(Eigen::SparseMatrix<unsigned char, Eigen::ColMajor> sparse_matrix, int cols)
{
    std::vector<std::vector<int>> curlevel_allchild;
    std::vector<int> child_id;
    for(int i=0; i<sparse_matrix.rows(); i++){
        child_id.push_back(i+1);
    }
    curlevel_allchild.push_back(child_id);
    Build(*this, sparse_matrix, cols, curlevel_allchild);
}

